
package org.spp.batchedAccess;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.apache.commons.math.util.MathUtils;

import org.spp.voronoi.Centroid;
import org.spp.voronoi.Edge;
import org.spp.voronoi.Vertex;
import org.spp.utilities.comparators.MaxDistEdgeComparator;
import org.spp.utilities.Point;


/**
 * BatchedAccess.java
 * @author Ilio Catallo, Eleonora Ciceri
 * @version 1.0
 * 
 * Description: the class applies the Batched Access method to a set of data. A
 *              budget consisting of the number of retrievable objects is given. 
 *              The class computes a set of radii with which objects are retrieved
 *              in a distance based access and a number of objects that will be 
 *              retrieved with score based access.
 * 
 * Date: Jul 14, 2011
 */
public class BatchedAccess {
    
    // Attributes
    private double M;
    private List<Vertex> vertexes;
    private List<Edge> edges;
    private List<Double> result;
    private int sampleInterval;
    private double epsilon;
    
    // Debug
    private int iterations = 0;
    
    /**
     * Constructor for the batched access class
     * @param epsilon
     */
    public BatchedAccess(double epsilon) {   
        this.sampleInterval = 30;
        this.epsilon = epsilon;
    }
    
    /**
     * Method that returns the vertex that is related to the i-th calculated radius
     * @param index 
     * @return vertex
     */
    public Vertex getVertex(int index) {
        return edges.get(index).getStartVertex();
    }
    
    /**
     * Method that returns the i-th calculated radius
     * @param index
     * @return radius
     */
    public Double getRadius(int index) {
        return result.get(index);
    }
    
    /**
     * Method that returns the budget that can be used to retrieve objects in score based access
     * @return Ms
     */
    public Double getScoreBudget() {
        return result.get(result.size()-1);
    }
    
    /**
     * Method that returns number of calculated radii
     * @return numRadii
     */    
    public int getNumRadii() {
        return edges.size();
    }
    
    /**
     * Method that initializes the class parameters: the budget and the vertexes on which calculate the radii
     * @param M
     * @param vertexes 
     */
    public void initialize(double M, List<Vertex> vertexes) {
        this.M = M;
        this.vertexes = vertexes; 
        this.edges = new ArrayList<Edge>();        
        this.result = new ArrayList<Double>();
    }
    
    
    /**
     * Method that computes the radii and the score budget used to retrieve objects
     * REMEMBER: the result given by this method is written in the form: [r_1...r_V M_s]
     * @param vertexes
     * @param M 
     * @param type
     * @param lambda
     * @param Smax 
     * @param a 
     * @param Sdepth 
     * @param rho 
     */
    public void computeRadiiAndBudget(List<Vertex> vertexes, double M, String type, double lambda, double Smax, double a, int Sdepth, double rho){
        // Variables                       
        double Md = 0;
        double Ms = 0;
        
        double[] taus = new double[sampleInterval+1];
        double[] taud = new double[sampleInterval+1];
        double[] tau = new double[sampleInterval+1];
        
        double bestTau = Double.POSITIVE_INFINITY;
        List<Double> bestR = new ArrayList<Double>();
        double bestMs = 0;
        
        int k = 0;

        initialize(M, vertexes);
        
        // Retrieve the best edge for each vertex 
        // NOTE: at the end we will have two lists, the first one containing the
        // vertexes and the second one containing the best edges. Choosing a specific
        // index i with which pick up an object from each of the lists will lead to
        // the couple <vertex(i), bestEdgeForVertex(i)>
        for (int i = 0; i < vertexes.size(); i++) {
            computeDistanceFunction(vertexes.get(i));
            edges.add(computeIntraVertexBestRadii(vertexes.get(i)));
        }
        
        // Selection of the access method
        if (type.equals("dist")) {
            Md = M;
            Ms = 0;
            
            result = computeRadii(Md, rho);
            result.remove(result.size()-1); // Remove tau_d from the results' array
            result.add(Ms);
        }
        
        if (type.equals("score")) {
            Ms = M;
            Md = 0;

            for (int i = 0; i < vertexes.size(); i++)
                result.add(0.0);              

            result.add(Ms);
        }
            
        if (type.equals("distScore")){
            while (Md <= M) {
                Ms = M - Md;

                result = computeRadii(Md, rho);

                // Retrieve the threshold for the distance part
                taud[k] = result.get(result.size()-1); 
                result.remove(result.size()-1); 

                // Compute the threshold for the score part
                taus[k] = Smax * (1 - a*(Sdepth + Ms));

                // Compute the total threshold
                tau[k] = (1 - lambda)*taus[k] + lambda*taud[k];

                if (tau[k] < bestTau) {
                    bestTau = tau[k];
                    bestR = result;
                    bestMs = Ms;
                }

                Md = Md + (M / sampleInterval);
                k++;
            }

            result = bestR;
            result.add(bestMs);
        }
        
    }
    
    /**
     * Method that computes the coefficients for the distance function along an edge.
     * The results are stored in the edge.
     * @param vertex
     */    
    private void computeDistanceFunction(Vertex vertex) {
        
        for (int i = 0; i < vertex.getEdges().size(); i++) {
            Edge currentEdge = vertex.getEdges().get(i);
            
            if (currentEdge.getMinDistance() > 0) {
                Centroid centroid = currentEdge.getCentroid();
                double[] direction = currentEdge.getDirection();
                double[] vertexToCentroid = centroid.computeVectorToPoint(vertex);
                
                double x1 = Point.dotProduct(vertexToCentroid, direction);
                double x2 = Math.sqrt(Math.pow(MathUtils.safeNorm(vertexToCentroid),2.0) - Math.pow(x1,2.0));
                
                double[] distanceCurveCoefficients = {(-2*x1), 
                                                      (Math.pow(x2, 2.0) + Math.pow(x1, 2.0))};
                
                currentEdge.setDistanceCoefficients(distanceCurveCoefficients);
            }
        }
    
    }
    
    /**
     * Method that selects the best edge for each vertex (in terms of distance: the
     * selected edge will be the only one that will be analyzed, since the other
     * distance functions will be redundant if compared to this one)
     * @param vertex
     * @return bestEdge
     */    
    private Edge computeIntraVertexBestRadii(Vertex vertex) {
        // Variables
        double distanceMaxMin = Double.NEGATIVE_INFINITY;
        Edge chosenEdge = null;
        
        for (int i = 0; i < vertex.getEdges().size(); i++) {
            Edge currentEdge = vertex.getEdges().get(i);
            
            if (currentEdge.getMinDistance() > 0) {
                double b = currentEdge.getDistanceCoefficients()[0];
                double c = currentEdge.getDistanceCoefficients()[1];
                double R = currentEdge.getMinDistance();
                
                double distance = Math.pow(R, 2.0) + b * R + c;
                
                if (distanceMaxMin < distance) {
                    distanceMaxMin = distance;
                    chosenEdge = currentEdge;
                }
            }
        }
        
        return chosenEdge;
    }
        
    /**
     * Method that computes the radii for the batched access method.
     * REMEMBER: the result given by this method is written in the form: [r_1...r_V tau_d]
     * @param Md 
     * @param rho
     * @return radii
     */        
    private List<Double> computeRadii(double Md, double rho) {
        // Variables
        List<Double> result = new ArrayList<Double>();
        MaxDistEdgeComparator comparator = new MaxDistEdgeComparator();
        
        // Sort the edges
        Collections.sort(edges, comparator);
        
        // If the budget is 0 then the radii will be all equal to 0
        if (Md == 0) {
            for (int i = 0; i < edges.size(); i++)
                result.add(0.0);
            
            double tauMax = edges.get(0).getDistanceCoefficients()[1];
            // Add tau
            result.add(tauMax);
            return result;
        }
        
        // Compute the limits for the recursive research
        double bMax = edges.get(0).getDistanceCoefficients()[0];
        double cMax = edges.get(0).getDistanceCoefficients()[1];
        double upperBoundDistance = cMax;
        
        double bMin = edges.get(edges.size()-1).getDistanceCoefficients()[0];  
        double cMin = edges.get(edges.size()-1).getDistanceCoefficients()[1];
        double lowerBoundDistance = Math.pow(bMin/(-2),2.0) + bMin*(bMin/(-2)) + cMin;
        
        result = binarySearch(Md, rho, upperBoundDistance, lowerBoundDistance);   
        System.out.println("-> Si sono richieste " + iterations + " iterazioni.");
        iterations = 0;
        
        return result;
    }
    
    /**
     * Method that recursively computes the radii
     * @param Md
     * @param rho 
     * @param upperBoundDistance
     * @param lowerBoundDistance 
     * @return radii
     */ 
    private List<Double> binarySearch(double Md, double rho, double upperBoundDistance, double lowerBoundDistance) {
        // Variables
        List<Double> result = new ArrayList<Double>();
        
        iterations ++;
        
        if (lowerBoundDistance > upperBoundDistance) {
            result.add(-1.0);
            return result;
        }
        
        double tau = (lowerBoundDistance + upperBoundDistance) / 2;
        result = computeSolution(tau);
        double cost = computeCost(result, rho);
        
        if (cost > Md)
            result = binarySearch(Md, rho, upperBoundDistance, tau);
        else
            if (cost < Md - epsilon)
                result = binarySearch(Md, rho, tau, lowerBoundDistance);
            else
                result.add(tau);     // Adds the tau_d only at the end of the iterations   
        
        return result;
    }
    
    /**
     * Method that computes the cost for the access to the objects using the current calculated radii
     * @param result
     * @param rho
     * @return cost
     */     
    private double computeCost(List<Double> result, double rho) {
        // Variables
        double cost = 0;
        int dimension = 0;
        
        if (edges.get(0).getStartVertex().getCoordinates().length == 2)
            dimension = 2;
        
        if (edges.get(0).getStartVertex().getCoordinates().length == 3)
            dimension = 3;
        
        for (int i = 0; i < result.size(); i++) {
            double factor = edges.get(i).getStartVertex().getFactor();
            
            if (dimension == 3)
                cost += rho*(4.0/3.0)*Math.PI*factor*Math.pow(result.get(i),3.0);
            
            if (dimension == 2)
                cost += rho*Math.PI*factor*Math.pow(result.get(i),2.0);
        }
        
        return cost;
            
    }
    
    /**
     * Method that computes and stores the radii corresponding to the computed threshold
     * @param tau
     * @return radii
     */     
    private List<Double> computeSolution(double tau) {
        // Variables
        List<Double> result = new ArrayList<Double>();
        
        for (int i = 0; i < edges.size(); i++) {
            double b = edges.get(i).getDistanceCoefficients()[0];
            double c = edges.get(i).getDistanceCoefficients()[1];
            
            double Rmax = b/(-2);
            double distanceMax = c;
            double distanceMin = Math.pow(Rmax,2.0) + b*Rmax + c;
            
            if (tau > distanceMax)
                result.add(0.0);
            else
                if (tau < distanceMin)
                    result.add(Rmax);
                else
                    result.add((- b - Math.sqrt(Math.pow(b,2.0)-4*c+4*tau))/2);
        }   
        
        return result;
    }
    
}
